package Solution_Initiale;
/*
* Nom de classe : BinPacking
*
* Description : donn≈Ωes et algorithmes pour un problÔøΩme de bin-packing
*
* Version : 1.0
*
* Date : 04/02/2013
*
* Auteur : Chams LAHLOU
*/

import java.util.*;
import java.io.*; // pour les accÔøΩs aux fichiers

import Algo_Memetic.AlgorithmeMemetic;
import Algo_Memetic.Individu;
import Algo_Memetic.Population;

public class BinPacking {
	public static ListeElements Elements;		// ≈Ωl≈Ωments ÀÜ placer dans les bo‚Äùtes
	public static int capacite;				// capacit≈Ω des bo‚Äùtes
	private int valeurSolution;			// valeur d'une solution
	private ListeBoites solution;		// liste des bo‚Äùtes d'une solution
	
	// constructeur par d≈Ωfaut
	public BinPacking() {
		capacite = 0;
		Elements = null;
		valeurSolution = 0;
		solution = null;
	}

	// constructeur 2 (problÔøΩme avec une bo‚Äùte vide au d≈Ωpart)
	public BinPacking(int capacite) {
		this.capacite = capacite;
		Elements = new ListeElements();
		valeurSolution = 1;
		solution = new ListeBoites();
		solution.ajouterBoite(capacite);
	}

	// constructeur 3 : ÀÜ partir d'un fichier de donn≈Ωes
	public BinPacking(String s) {
		System.out.println("lecture du fichier " + s);
    	try {
    		Scanner scanner = new Scanner(new FileReader(s));
    		
    		// lecture de la capacit≈Ω des bo‚Äùtes
    		if (scanner.hasNextInt()) {
    			capacite = scanner.nextInt();
    		}

    		valeurSolution = 1;
    		solution = new ListeBoites();
    		solution.ajouterBoite(capacite);

    		Elements = new ListeElements();

    		// lecture des tailles des ≈Ωl≈Ωments
    		while (scanner.hasNextInt()) {
    			ajouterElement(scanner.nextInt());
    		}
    		
    		scanner.close();
    	}
    	catch (IOException e) {
    		System.err.println("Erreur : " + e.getMessage()) ;
    		System.exit(2) ;
    	}
    }

	public int getNbElements() {
		return Elements.getNbElements();
	}
		
	public int getNbBoites() {
		return solution.getNbBoites();
	}
		
	public int getCapacite() {
		return capacite;
	}
	
	public ListeElements getElements() {
		return Elements;
	}
		
	// renvoie l'≈Ωl≈Ωment d'indice i
	public Element getElement(int i) {
		return Elements.getElement(i);	
	}

	public ListeBoites getSolution() {
		return solution;
	}

	// renvoie la bo‚Äùte d'indice i
	public Boite getBoite(int i) {
		return solution.getBoite(i);
	}
	
	// fixe une solution et sa valeur
	public void setSolution(ListeBoites lb) {
		ListeElements l = new ListeElements();
		valeurSolution = borneInf(lb, l);
		solution = lb.copie();
	}
	
	// ajoute un nouvel ≈Ωl≈Ωment au problÔøΩme
	public void ajouterElement(int taille) {
		Element e = new Element(getNbElements()+1, taille);
		Elements.ajouterElement(e);
	}

	// affiche le contenu des bo‚Äùtes
	public void afficherSolution() {
		int n = getNbBoites();
        for (int i=1; i <= n; i++) {
        	Boite b = getBoite(i);
        	b.afficher();
        	System.out.println();
        }
    }

	// affiche les ≈Ωl≈Ωments : (num≈Ωro, taille)
	public void afficherElements() {
		int n = getNbElements();
        for (int i = 1; i <= n; i++) {
        	Element e = getElement(i);
        	System.out.print("(" + e.getNumero() + "," + e.getTaille() + ")  ");
        }
    }

	// EXO 3
	// place l'≈Ωl≈Ωment num≈Ωro i dans la bo‚Äùte num≈Ωro j
	public void placerElement(int i, int j) {			
			Element e = this.Elements.getElement(i);
			this.solution.getBoite(j).ajouterElement(e);
	}
	
	// EXO 4
	// calcul d'une borne inf≈Ωrieure connaissant une liste de bo‚Äùtes
	// et une liste d'≈Ωl≈Ωments ÀÜ placer
	// Remarque : si la liste est vide on obtient une valeur exacte de la solution
	public int borneInf(ListeBoites lb, ListeElements le) {
		int poidTot = 0;
		if(!le.getListe().isEmpty() && !lb.getListe().isEmpty()){	
			//On calcule le poid total des objets √†, placer
			for(int j=1; j<=le.getNbElements();j++){
				poidTot= poidTot+le.getElement(j).getTaille();
			}
			//Puis on retire la place disponible dans le boites
			for(int k=1; k<=lb.getNbBoites();k++){
				poidTot= poidTot-lb.getBoite(k).getPlaceLibre();
			}
			//On Traite le cas o√π il y a plus de place libre que d'objets √† placer
			if(poidTot<=0){
				poidTot=0;
			}
		}
		//Il faut alors au mimimum le poids total √† placer divis√© par la capacit√© des boites.
		return lb.getNbBoites()+ (int)(Math.ceil(poidTot/(double)capacite));	
	}

	// EXO 5
	// Algorithme First-Fit appliqu≈Ω ÀÜ une liste d'≈Ωl≈Ωments pass≈Ωe en paramÔøΩtre
	// renvoie la liste de bo‚Äùtes remplies
	public ListeBoites algoFirstFit(ListeElements l) {
		int ObjetCourant = 1;		
		//On parcourt tout les objets de la liste
		while(ObjetCourant<=l.getNbElements()){	
			int boiteCourante = 1;
			//On parcourt toutes les boites jusqu'√† ce qu'on en trouve une avec de l'espace suffisant
			//Ou jusqu'√† ce qu'il n'y en ait plus
			while(boiteCourante<=valeurSolution && this.getBoite(boiteCourante).getPlaceLibre()<l.getElement(ObjetCourant).getTaille()){
				boiteCourante = boiteCourante++;
				boiteCourante++;
			}
			//S'il n'y avait aucune boite avec assez d'espace on en cr√©e une nouvelle
			if(boiteCourante>valeurSolution){
				this.solution.ajouterBoite(this.capacite);
				valeurSolution++;
			}
			//S'il y avait une boite avec assez d'espace on met l'objet dedans.
			if(this.getBoite(boiteCourante).getPlaceLibre()>=l.getElement(ObjetCourant).getTaille()){
				this.getBoite(boiteCourante).ajouterElement(l.getElement(ObjetCourant));
			}
			//On passe ensuite √† l'objet suivant.
			ObjetCourant++;	
		}
			return this.solution;		

	}

	// EXO 6
	// Algorithme Best-Fit appliqu≈Ω ÀÜ une liste d'≈Ωl≈Ωments pass≈Ωe en paramÔøΩtre
	// renvoie la liste des bo‚Äùtes remplies
	public ListeBoites algoBestFit(ListeElements l) {
		int ObjetCourant = 1;	
		//On parcourt tout les objets de la liste
		while(ObjetCourant<=l.getNbElements()){	
			//System.out.println("On consid√®re l'objet "+ ObjetCourant+", de taille "+ l.getElement(ObjetCourant).getTaille());
			//permet de savoir s'il y a une boite de libre
			boolean IlYAUneBoite = false;
			//Variable temporaire qui permet de savoir quel est l'espace libre le plus petit
			//On l'intialise √† 10000 pour mat√©rialiser l'infini
			int temp=100000;
			//Variable temporaire qui permet de savoir qu'elle la boite dont l'esapce associ√©
			//valide est le plus optimale
			int boiteTemp=1;
			//On parcourt toutes les boites
			for(int k=1;k<=this.getNbBoites();k++){
				//S'il y a assez d'espace dans une boite avec assez d'espace
				if(this.getBoite(k).getPlaceLibre()>=l.getElement(ObjetCourant).getTaille()){
					IlYAUneBoite=true;
					//On regarde si l'espace est plus petit que celui qu'on aurait d√©j√† trouv√©
					if(temp>this.getBoite(k).getPlaceLibre()){
						temp=this.getBoite(k).getPlaceLibre();						
						boiteTemp = k;
					}
				}
			}	
			//System.out.println("Y'a t-il une boite avec suffisament d'espace ? "+IlYAUneBoite );
			//S'il n'y a aucune place dans une aucune des boties on en cr√©e une nouvelle
			if(IlYAUneBoite == false){
				this.solution.ajouterBoite(this.capacite);
				valeurSolution++;
				//System.out.println("On a rajout√© une boite.");
				this.getBoite(this.solution.getNbBoites()).ajouterElement(l.getElement(ObjetCourant));
			}
			//Sinon on rajoute l'√©l√©ment dans la boite la plus d'espace disponible minimal.
			else{
				//System.out.println("On a rajout√© l'√©l√©ment " + ObjetCourant +", dans la boite "+ boiteTemp);
				this.getBoite(boiteTemp).ajouterElement(l.getElement(ObjetCourant));
			}
			
			//On passe ensuite √† l'objet suivant.
			//this.solution.afficher();
			ObjetCourant++;	
		}
			return this.solution;
	}
	
	// proc≈Ωdure de recherche par ≈Ωvaluation et s≈Ωparation de Eilon et Christofides 1971
	// (appel initial)
	public void algoSeparationEvaluation() {

		ListeElements le = getElements().copie();
		le.trierTaillesDecroissantes();
		ListeBoites lb = new ListeBoites();
		//On calcule une premi√®re solution, qui nous permettra d'initialiser l'algorithme
		//avec Best-Fit
		ListeBoites init = this.algoBestFit(le);
		System.out.println("\n"+"La solution a √©t√© intialis√©e avec Best-Fit √† "+ this.valeurSolution+ " boites");
		System.out.println("\n"+"La solution initiale est :"+"\n");
		init.afficher();
		this.setSolution(init);
		algoSEP(lb, le);
	}
	
	// EXO 7
	// lBoites = liste des bo‚Äùtes utilis≈Ωes
	// lElements = liste des ≈Ωl≈Ωments ÀÜ placer
	// (appels suivants = partie r≈Ωcursive pour la recherche en profondeur)
	public void algoSEP(ListeBoites lBoites, ListeElements lElements){
		ListeBoites ListeBoiteCopie = lBoites.copie();
		ListeElements ListeElementsCopie = lElements.copie();
		//On commence par trier les √©l√©ments par taille d√©croissante
		ListeElementsCopie.trierTaillesDecroissantes();
		ListeBoiteCopie.trierPlacesLibresCroissantes();
		
		//On traite le cas o√π la liste est vide
		if(ListeElementsCopie.getNbElements()==0){
			//Si c'est le cas et que cette solution est meilleure on r√©actualise la valeur de 
			//la solution
			if(ListeBoiteCopie.getNbBoites()<this.valeurSolution){
				System.out.println("\n");
				System.out.println("La valeur de la solution a √©t√© mise √† jour.");
				this.valeurSolution=ListeBoiteCopie.getNbBoites();
				this.setSolution(ListeBoiteCopie);
			}
		}
		else{
			//On chercher une borne inf√©rieure du nombre de boites n√©c√©ssaires pour placer les objets
			//restants. Cela permet de couper des branches, et de ne pas explorer toutes les solutions.
			if(borneInf(lBoites,lElements)<=this.valeurSolution){
				//System.out.println(ListeBoiteCopie.getNbBoites());
				//On parcourt toutes les boites
				for(int k=1; k<=ListeBoiteCopie.getNbBoites();k++){
					//S'il y a de la place disponible dans la boite k on rajoute l'√©l√©ment courant
					if(ListeBoiteCopie.getBoite(k).getPlaceLibre()>=ListeElementsCopie.getElement(1).getTaille()){
						ListeBoiteCopie.getBoite(k).ajouterElement(ListeElementsCopie.getElement(1));
						//On retire ensuite l'√©l√©ment de la liste des √©l√©ments √† rajouter
						ListeElementsCopie.getListe().remove(0);
						//ListeBoiteCopie.afficher();
						//On r√©aplique algoSEP
						algoSEP(ListeBoiteCopie,ListeElementsCopie);
						//Pour le tour suivant on reprend les anciennes valeur de listeBoiteCopie et 
						//ListeElementsCopie
						ListeBoiteCopie = lBoites.copie();
						ListeElementsCopie = lElements.copie();
					}
				}	
			/*
			 * On traite ici le cas o√π on rajoute une nouvelle boite 
			 */
				ListeElementsCopie = lElements.copie();
				//on rajoute une boite
				ListeBoiteCopie.ajouterBoite(this.capacite);
				//Et on rajoute l'√©l√©ment courant dedans :	
				ListeBoiteCopie.getBoite(ListeBoiteCopie.getNbBoites()).ajouterElement(ListeElementsCopie.getElement(1));
				ListeElementsCopie.getListe().remove(0);
				//On r√©aplique SEP
				algoSEP(ListeBoiteCopie,ListeElementsCopie);
			}
		}
	}
	
	public ListeBoites algoFirstFit2(ListeElements l) {
		// A REMPLIR
		ListeBoites liste = new ListeBoites();
		liste.ajouterBoite(capacite);
		for (int i = 1; i <= l.getNbElements(); i++) {
			boolean b = true;
			for (int p = 1; p <= liste.getNbBoites(); p++) {
				if (liste.getBoite(p).getPlaceLibre() >= l.getElement(i).getTaille() && b) { //on range p dans la 1ere boite possible trouvee et aucune autre
					liste.getBoite(p).ajouterElement(l.getElement(i));
					b = false;
				}
			}
			if (b) {		//si on avait pas la place pour ranger l'objet on crée une nouvelle boite
				liste.ajouterBoite(capacite);
				liste.getBoite(liste.getNbBoites()).ajouterElement(l.getElement(i));
			}
		}
		return liste;
	}
	
	public static void main(String[] args) throws OutOfArrayException{
		BinPacking test = new BinPacking(10);		
		// Création d'un petit probleme pour test
		
		Boite boite=new Boite(1, 10);
		Boite boite2=new Boite(2, 10);
		Boite boite3=new Boite(3, 10);
		Element e1=new Element(1, 4);      
		Element e2=new Element(2, 5);	
		Element e3=new Element(3, 8);
		Element e4=new Element(4, 1);	
		Element e5=new Element(5, 6);
		boite.ajouterElement(e1);
		boite.ajouterElement(e2);
		boite2.ajouterElement(e4);
		boite2.ajouterElement(e5);
		boite3.ajouterElement(e3);
		Elements.ajouterElement(e1);
		Elements.ajouterElement(e2);
		Elements.ajouterElement(e3);
		Elements.ajouterElement(e4);
		Elements.ajouterElement(e5);
		
		// Test des affichages et de la conversion de la représentation ListeBoite
		// vers Individu et inversement
		
		ListeBoites lb=new ListeBoites();
		lb.setBoite(boite);
		lb.setBoite(boite2);
		lb.setBoite(boite3);
		Individu i=lb.toIndividu();
/*		System.out.println(lb.toString());
		System.out.println(i.affichageFormeTableau());
		System.out.println(i.toListeBoites().toString());*/
		int[] tab=new int[5];
		tab[0]=1;
		tab[1]=3;
		tab[2]=2;
		tab[3]=2;
		tab[4]=1;
		Individu i1=new Individu(tab, capacite);
/*		System.out.println(i1.affichageFormeTableau());
		System.out.println(i1.toString());*/
		
		// Test de l'affichage d'une population
		
		ListeBoites lb1=test.algoBestFit(Elements);
		Individu i2=lb1.toIndividu();
		ArrayList<Individu> pop=new ArrayList<Individu>();
		pop.add(i);
		pop.add(i2);
		Population p=new Population(pop);
//		System.out.println(p.toString());
		
		// Test de generateInitialPopulation
		
//		System.out.println(lb1.toString());
		AlgorithmeMemetic al=new AlgorithmeMemetic(test);
		System.out.println(al.generateRandomPopulation(5).toString());
		
		// Test de l'opérateur mutation : it works !
		
/*		Individu u=test.algoFirstFit2(BinPacking.Elements).toIndividu();
		System.out.println(u.toString());
		System.out.println("Solution : "+u.nbBoitesNonVide());
		Individu u1=AlgorithmeMemetic.mutation(u, 1);
		System.out.println(u1.toString());
		System.out.println("Solution : "+u1.nbBoitesNonVide());
		Individu u2=AlgorithmeMemetic.mutation(u1, 1);
		System.out.println(u2.toString());
		System.out.println("Solution : "+u2.nbBoitesNonVide());
		Individu u3=AlgorithmeMemetic.mutation(u2, 1);
		System.out.println(u3.toString());
		System.out.println("Solution : "+u3.nbBoitesNonVide());*/
		}
}